package graph;

import org.junit.Test;

import java.util.*;
import java.util.function.Function;

/*
 *@description 单词接龙
 *@author hkfan
 *@version 1.0
 *@create 2025/6/23 15:03
 */
public class LeetCode_127 {





    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //1. 新建map
        HashMap<String,List<String>> patternMap = new HashMap<>();
        //2. 边加入patternMap
        for (int i = 0; i < beginWord.length(); i++) {
            String str = beginWord.substring(0,i)+"*"+beginWord.substring(i+1);
            patternMap.computeIfAbsent(str, p->new ArrayList<>()).add(beginWord);
        }
        for (String word : wordList) {
            for (int i = 0; i < word.length(); i++) {
                String str = word.substring(0,i)+"*"+word.substring(i+1);
                patternMap.computeIfAbsent(str, p->new ArrayList<>()).add(word);
            }
        }
        if (!wordList.contains(endWord)){
            return 0;
        }
        //4. 返回结果
        return search(beginWord,endWord,patternMap);
    }

    private int search(String beginWord, String endWord, HashMap<String, List<String>> map) {
        //1. 定义
        Queue<String> queueStart = new ArrayDeque<>();
        Queue<String> queueEnd = new ArrayDeque<>();
        Map<String,Integer> visitedStart = new HashMap<>();
        Map<String,Integer> visitedEnd = new HashMap<>();
        queueStart.add(beginWord);
        visitedStart.put(beginWord, 1);
        queueEnd.add(endWord);
        visitedEnd.put(endWord, 1);
        //2. 循环
        while (!queueStart.isEmpty() && !queueEnd.isEmpty()){
            // 从起点方向扩展
            int result = expandLevel(queueStart, visitedStart, visitedEnd,map);
            if (result != -1) return result;

            // 从终点方向扩展
            result = expandLevel(queueEnd, visitedEnd, visitedStart,map);
            if (result != -1) return result;
        }
        return 0;
    }

    private int expandLevel(Queue<String> queue, Map<String, Integer> visitedStart, Map<String, Integer> visitedEnd,HashMap<String, List<String>> patternMap) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String node = queue.poll();
            if (visitedEnd.containsKey(node)) {
                return visitedStart.get(node) + visitedEnd.get(node) - 1;
            }
            for (int j = 0; j < node.length(); j++) {
                String str = node.substring(0,j)+"*"+node.substring(j+1);
                for (String s : patternMap.get(str)) {
                    if (!s.equals(str) && !visitedStart.containsKey(s)){
                        visitedStart.put(s, visitedStart.get(node) + 1);
                        queue.add(s);
                    }
                }
            }
        }
        return -1;
    }

}
